package javatest;

import java.util.Arrays;

import util.BinarySearchUtil;

// 求数组中的逆序对
public class InversePairs {
    public static void main(String[] args) {
        int[] nums = {30, 20, -10, 8, -20};
        InversePairs object = new InversePairs();
        System.out.println(object.inversePairs(nums));
    }

    // 采用树状数组来做
    // 没有离散化
    int inversePairsWithoutDescretination(int[] array) {
        if (array == null) {
            return 0;
        }
        int length = array.length;
        int[] bit = new int[length + 1];
        int res = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            // 比当前值小的数目，所以是array[i], 如果是小于等于就是array[i] + 1
            int curCount = sum(bit, array[i]);
            System.out.println("curCount:" + curCount);
            update(bit, array[i] + 1, 1);
            res += curCount;
        }
        return res;
    }

    int inversePairs(int[] array) {
        if (array == null) {
            return 0;
        }
        int length = array.length;
        int[] bit = new int[length + 1];
        int res = 0;
        int[] copy = Arrays.copyOf(array, array.length);
        // 先对数组进行排序，做离散化
        Arrays.sort(copy);

        for (int i = array.length - 1; i >= 0; i--) {
            // 比当前值小的数目，所以是array[i], 如果是小于等于就是array[i] + 1
            int index = BinarySearchUtil.lowerBound(copy, array[i]);
            System.out.println("curIndex:" + index);
            int curCount = sum(bit, index);
            System.out.println("curCount:" + curCount);
            update(bit, index + 1, 1);
            res += curCount;
        }
        return res;
    }

    void build(int[] bit, int[] A) {
        for (int i = 1; i <= bit.length; i++) {
            update(bit, i, A[i]);
        }
    }

    private int lowBit(int n) {
        return n & (-n);
    }

    /**
     * 更新原数组index的数据，差值为delta
     */
    private void update(int[] bit, int index, int delta) {
        for (int i = index; i < bit.length; i = i + lowBit(i)) {
            bit[i] += delta;
        }
    }

    // 求0~k的和
    private int sum(int[] bit, int k) {
        int res = 0;
        for (int i = k; i > 0; i = i - lowBit(i)) {
            res += bit[i];
        }
        return res;
    }
}
